\chapter{Convolution}
\paragraph{}Cette partie explique plus précisément la structure ainsi
que les solutions techniques choisies pour implémenter les matrices de
convolutions de façon générique. Ici, nous traitons des convolutions
sur des images.
\section{Générique}
L'utilisation de la bibliothèque est très simple, il suffit de respecter les 7 étapes suivantes pour obtenir un code fonctionnel minimaliste.
\begin{enumerate}

\item Premièrement, il faut configurer et créer l'arborescence du
  projet. Le script shell ``configure'' va jouer ce rôle. Pour l'utiliser, il suffit de l'appeler depuis un terminal. L'architecture de la machine sera automatiquement prise en compte. Il faudra mettre les sources du projet dans le répertoire ``src''.
\begin{Verbatim}
user@computre:~/monprojet/> ./configure
\end{Verbatim}

\item Une fois le projet créé, il est nécessaire d'inclure le header
de la bibliothèque dans le fichier source, afin d'avoir accès aux classes et structures nécessaires.
\begin{Verbatim}
#include "convolution.hh"
\end{Verbatim}

\item Ensuite, il faut définir la matrice de convolution. Elle
  doit être de type ``int'', carrée et de taille impaire\footnote{En
    effet, il est nécessaire d'avoir un élément central qui
    correspondra au pixel traité.}. Pour lui attribuer des valeurs, on utilisera l'opérateur \mbox{{\tt [ ]}} comme pour un tableau à deux dimensions.
\begin{Verbatim}
Matrix<int> matrix(size, size);
matrix[0][0] = x;
\end{Verbatim}

\item À l'étape suivante, il faut créer un objet Convolution. Le constructeur prend en paramètre la matrice de convolution définie précédemment, et un ``unsigned int'' contenant le diviseur.
\begin{Verbatim}
Convolution engine(matrix, diviseur);
\end{Verbatim}

\item Il faut également définir une image d'entrée et de sortie. Le principe étant généralement d'ouvrir une image existante et d'en créer une nouvelle en sortie. Les deux images doivent avoir la même taille.
\begin{Verbatim}
Image image("data/monimage.jpg");
Image result(image.width(), image.height());
\end{Verbatim}

\item Il suffit ensuite d'appeler la fonction de convolution ``convol'' en lui passant en paramètre l'image d'entrée et de sortie.
\begin{Verbatim}
engine.convol(image, result);
\end{Verbatim}

\item Pour finir, on sauvegarde la sortie avec la méthode ``save'' de la classe ``Image'' pour enregistrer l'image sur le disque dur en lui donnant en paramètre le chemin désiré. L'image de sortie sera en BMP.
\begin{Verbatim}
result.save("data/convolution-monimage.bmp");
\end{Verbatim}

\end{enumerate}

\section{Séquentiel}\label{ref_sequentiel}
Le calcul de convolution en séquentiel se fait simplement avec quatres boucles ``for'' imbriquées.
\begin{Verbatim}
Pour chaque ligne de l'image
  Pour chaque élément dans la ligne en cours
    initialiser les composantes r,g,b,a à 0

    //Parcours des voisins de l'élément courant de l'image à l'aide
    // de la matrice de convolution
    Pour chaque ligne de la matrice
      Pour chaque élément de la ligne de la matrice
         ajouter à r,g,b,a les valeurs des pixels correspondants 
         dans l'image, multiplié par la valeur de la case de la matrice.

    le pixel de sortie prend les valeurs des pixels voisins calculé 
    précédemment divisée par la valeur du diviseur fournit pour la 
    convolution.

\end{Verbatim}
\begin{figure}[h!]
  \centering
  \includegraphics[scale=0.5]{images/convolution}
  \caption{Illustration des opérations de convolution}
  \label{fig:opconv}
\end{figure}
\newpage
\section{Parallèle - Multi-Thread}
\paragraph{}Pour la parallèlisation du calcul sur multi-processeur, nous avons choisi une solution des plus simples : nous nous contentons de découper l'image en bandes de hauteur $h/T$, avec $h$ la hauteur de l'image et $T$ le nombre de threads, et d'effectuer le calcul en local sur chaque thread.
\paragraph{}Le nombre de threads étant assez limité et ne nécessitant que peu de synchronisations, nous avons choisi d'utiliser libpthread de manière à ne pas avoir à se soucier de tester d'autres moteurs multi-thread.
\section{Parallèle - CUDA}
\paragraph{}La mémoire présente sur les cartes graphiques étant beaucoup plus limitée que la RAM sur les machines, il est nécessaire de définir une technique pour découper l'image. De plus les données devant être envoyées à la carte graphique, traitées, puis rapatriées dans la RAM, il faut définir une manière de limiter le poids des transferts pour gagner au maximum sur le calcul. Les parties suivantes définissent les solutions utilisées pour répondre à ces problématiques.
\subsection{Découpage}
\paragraph{}Les blocs de données sont définis par deux paramètres : la
taille et la position du bloc à traiter ainsi que la taille et la
position du bloc nécessaire à son traitement. En effet chaque donnée à
besoin de tous ses voisins (voir section \ref{ref_sequentiel}). La zone à prendre en compte de chaque côté du bloc à traiter est $\lfloor \frac{matricedim}{2} \rfloor$.

\newpage

\paragraph{Caractéristiques physiques}
\paragraph{}Les dimensions de notre découpage tiennent compte des paramètres physiques du matériel graphique. En particulier, il faut prendre en compte le nombre de multi-processeurs sur la carte ainsi que la mémoire disponible, nous avons également paramétré un nombre de threads par multi-processeur.
\paragraph{}Le choix du nombre de threads par multi-processeurs est
assez complexe. En effet, les multiprocesseurs exécutent
simultanément 16 threads mais sont capables d'en émuler beaucoup plus
(jusqu'à 1024). En particulier dans notre implémentation nous avons
choisi de lancer 96 threads par Multi-Processeur (voir section \ref{ref_benchmarks}). Cependant, il est difficile de faire un vrai choix car les gains de performances sont différents d'une carte à une autre (voir même sur des images différentes).
\paragraph{}De la même manière, chaque multi-processeur physique est capable d'en émuler plusieurs. Nous ne sommes pas encore fixés sur le choix du nombre de multi-processeurs à émuler, les performances étant différentes d'une carte à une autre. Sur les {\Large \textsc{nVidia}} GTX 480 utilisées à l'université, nous avons fixé cette valeur à trois fois le nombre de multi-processeurs physiques.
\paragraph{Calcul des dimensions maximales}
\paragraph{}$$largeur\_bloc\_out=MPS*NB\_THREADS $$
\paragraph{}$$largeur\_bloc\_in=(MPS*NB\_THREADS)+2*\lfloor \frac{matricedim}{2} \rfloor$$
\paragraph{}Avec $MPS$ le nombre de multi-processeurs à émuler,
$NB\_THREADS$ le nombre de threads à lancer sur chaque
multi-processeur (émulé) et $matricedim$ la taille de notre matrice de
convolution.
\paragraph{}$$hauteur\_bloc\_in=\frac{MAXMEM}{4*largeur\_bloc\_in}$$
\paragraph{}Avec $MAXMEM$ la taille maximale de la mémoire que nous
avons décidé d'allouer et 4 le nombre de composantes unsigned char
d'un pixel.
\paragraph{}$$hauteur\_bloc\_out=\frac{MAXMEM}{4*largeur\_bloc\_in}-2*\lfloor \frac{matricedim}{2} \rfloor$$
\paragraph{}En effet, nous retranchons $2*\lfloor \frac{matricedim}{2} \rfloor$ pour obtenir la longueur maximale d'un bloc de sortie.
\begin{Verbatim}
    wblockmax_out = NB_THREADS*MPS;
    wblockmax_in = wblockmax_out+(2*(matrix.width()/2)); 

    hblockmax_in = MAXMEM/(wblock_in*sizeof(pixel));
    hblockmax_out = hblock_in-(2*(matrix.width()/2));
\end{Verbatim}
\paragraph{Calcul des positions et des dimensions réelles des blocs}
\paragraph{}On commence par calculer le nombre de blocs à créer en largeur ({\tt x}) et en hauteur ({\tt y}) sur l'image, cela consiste simplement en une division de la largeur totale par la largeur d'un bloc et de même pour la hauteur (la seconde partie du calcul représente le case particulier des derniers blocs en largeur/hauteur).
\begin{Verbatim}
unsigned int x = (data.width()-2*(matrix.width()/2))/wblockmax_out + 
   (((data.width()-2*(matrix.width()/2))%wblockmax_out) > 0);
unsigned int y = (data.height()-2*(matrix.width()/2))/hblockmax_out + 
   (((data.height()-2*(matrix.width()/2))%hblockmax_out) > 0);

\end{Verbatim}
\paragraph{}On définit ensuite les positions du bloc de cette manière :
\begin{Verbatim}
for(unsigned int i = 0; i < y; i++)
  for(unsigned int j = 0; j < x; j++){
    coord_data c;
	
    c.bxo = start+j*wblockmax_out;
    c.bxi = c.bxo-start;

    c.byo = start+i*hblockmax_out;
    c.byi = c.byo-start;
  }
\end{Verbatim}
\paragraph{}Avec {\tt c.bxo}, la position du bloc de sortie en x, {\tt c.byo}, la position du bloc de sortie en y et {\tt c.bxi} et {\tt c.byi} leurs équivalents pour le bloc d'entrée.
\paragraph{}Les tailles réelles des données du bloc (celles qui seront transmises à la carte graphique) sont les tailles maximales définies ci-avant, hormis pour les blocs se trouvant au bord droit de l'image et au bord haut de l'image (on n'a pas besoin de données extérieures à l'image car on arrête le calcul de la sortie avant le bord).
\paragraph{}Les positions et les tailles de nos données sont maintenant bien définies, nous pouvons les envoyer et les traiter.
\subsection{Streaming - utilisation Pinned-Memory}
\paragraph{Stream}
\paragraph{}Le traitement d'un bloc de donnée est fait de la manière suivante :
\begin{Verbatim}
envoyer le bloc à la carte graphique
traiter le bloc dans la carte graphique
ramener le bloc dans la RAM
\end{Verbatim}
\paragraph{}Le problème ici est que nous devons attendre à chaque fois que les transferts aller et retour soit terminés pour commencer le calcul d'un nouveau bloc.
\paragraph{}Le SDK CUDA contient un mécanisme de stream pour effectuer les transferts et les calculs de manière asynchrone, cela nous permet de mettre en place un système de double-buffering. L'idée étant de lancer le chargement d'un bloc, puis d'effectuer dans le même temps le calcul du bloc chargé et le transfert du bloc suivant. Le code est assez simple à mettre en place.
\begin{Verbatim}
creer 2 buffers d'entree
creer 2 buffers de sortie
creer 2 stream

pour chaque bloc
  remplir buffer d'entree numero block%2 sur le stream block%2
  traiter le block%2 sur le stream block%2
  rappatrier buffer de sortie numero block%2 sur le stream block%2
\end{Verbatim}
\paragraph{}Ce pseudo code peut, certes, paraître simpliste mais hormis la syntaxe un peu lourde de CUDA, la traduction est instantanée.
\paragraph{Pinned Memory}
\paragraph{}Pour accélérer les transferts dans le cadre de l'utilisation des streams CUDA et de l'asynchronisme des copies vers la carte graphique, {\Large \textsc{nVidia}} oblige l'utilisation de la ``page-locked memory'', cette mémoire présente la particularité de ne pas pouvoir être mise en swap par le système. De cette manière la carte graphique peut accéder directement aux zones mémoire physique sans faire de demande particulière au système d'exploitation.
\paragraph{}{\Large \textsc{nVidia}} indique que les performances de la ``page-locked
memory'' sont meilleures mais nous ne pouvons pas le vérifier puisqu'il est impossible d'utiliser les streams et les copies asynchrones sans l'utiliser.
\subsection{Calcul - utilisation des Textures}
\paragraph{}Pour accélérer les accès aux données d'entrées (qui ne sont jamais modifiées au cours du calcul), nous avons décidé de tirer parti des possibilités présentes sur les cartes graphiques : l'utilisation des unités de texture. 
\paragraph{}En effet, les cartes graphiques ont intrinsèquement tous les mécanismes physiques nécessaires à l'accès rapide à des données fixes. La mise en texture des données nécessite quelques artifices techniques mais permet de simplifier fortement l'accès aux données d'entrée et de tirer parti de la mise en cache conçue pour les accès texture.
\paragraph{}La première contrainte pour l'utilisation des textures est la nécessité de transformer notre buffer d'entrée en un buffer 2D (les textures 1D ont un volume de donnée beaucoup trop mince pour être utilisable). La structure en question est le type cudaArray et s'alloue avec une fonction spécifique.
\paragraph{}La seconde contrainte est d'avoir une variable globale servant à faire la liaison du buffer 2D en tant que texture.
\paragraph{}L'utilisation de ce système s'effectue donc de la manière suivante :
\begin{Verbatim}
allouer le buffer 2D
remplir le buffer 2D
lier le buffer 2D a la reference de texture
effectuer le calcul
délier le buffer 2D
\end{Verbatim}
\paragraph{}L'accès à la texture est ensuite effectué par l'appel à une fonction prenant en paramètre la référence de texture, la position sur x et sur y.
\paragraph{}Il est important de noter qu'il ne semble pas possible de
créer des buffers 2D d'une certaine longueur en fonction de sa hauteur
et inversement. Néanmoins aucune documentation n'en parle et il est
impossible de déterminer précisément la relation entre les deux. Nous
avons donc défini des valeurs multiples de $32$ plus $1$ et
proportionelles aux nombres de threads.
\subsection{Calcul - utilisation de la mémoire Shared}
\paragraph{}Pour limiter le nombre d'accès au buffer de sortie depuis les kernels (données que l'on peut qualifier de ``lointaines''), nous avons tiré parti d'une autre possibilité de CUDA : la mémoire shared des multi-processeurs. Cette mémoire est comparable au cache des processeurs en terme de performances mais doit être gérée explicitement par le programmeur sur le GPU.
\paragraph{}Cependant, cette mémoire est très limitée (par exemple sur la GTX 480 il n'y a que $16ko$ disponibles) sachant qu'une partie de son volume est nécessaire au fonctionnement de CUDA mais aucune documentation n'est fournie à ce sujet.
\paragraph{}L'autre spécificité de cette mémoire est son système de banques. Ces banques, qui sont au nombre de 16, stockent les $i$ données d'une zone contigüe dans la $i\%16$ ème banque. 
\paragraph{}Par exemple :
\begin{figure}[h!]
  \centering
  \includegraphics[scale=0.35]{images/banks}
  \caption{Alignement mémoire banque}
\end{figure}
\paragraph{}Si plusieurs accès en écriture sont effectués sur une même banque (même donnée ou pas) ils seront séquentialisés, c'est pourquoi il faut garantir que les threads accèderont au maximum à des cases différentes.
\paragraph{}Pour cela nous avons déclaré un buffer sous forme d'un tableau en mémoire shared à deux dimension de longueur 33 et de hauteur $NB\_THREADS$. La boucle pour le remplissange de ce buffer est la suivante.
\begin{Verbatim}
for(unsigned int i = 0; i < 33 && j+i < h; i++){
  r = 0;
  g = 0;
  b = 0;
  a = 0;

  for(unsigned int l = 0; l < dim; l++)  
    for(unsigned int k = 0; k < dim; k++){
      //calculer rgba
    }
  
  tmp_out[numero_thread][i].r = (r > 0)*(r/divider);
  tmp_out[numero_thread][i].g = (g > 0)*(g/divider);
  tmp_out[numero_thread][i].b = (b > 0)*(b/divider);
  tmp_out[numero_thread][i].a = (a > 0)*(a/divider);
}
\end{Verbatim}
\paragraph{}Finalement chaque thread écrit toujours dans sa colonne du buffer. Comme la longueur des lignes est égale à 33, qui n'est pas multiple de 16, nous garantissons que dans chaque bloc, chacun des threads accède à une banque différente : les accès sont parallèles dans ce bloc de threads et donc non séquentialisés.
\paragraph{}Enfin, chaque fois que le buffer est plein, nous en recopions le contenu dans le buffer de sortie et nous recommençons autant de fois que nécessaire pour traiter la totalité du bloc d'entrée.
\subsection{Principaux problèmes rencontrés}
\paragraph{}Les fonctionnalités ci-dessus, si elles sont relativement
simples à mettre en \oe uvre, sont généralement accompagnées de contraintes relativement fortes en rapport avec la structure du code et la représentation des données en mémoire, il a souvent fallu faire des concessions sur la propreté du code pour garder une certaine efficacité.
\paragraph{}Plus encore que les contraintes de codage, le manque de documentation et la rareté d'exemples ``parlant'' au sujet de CUDA a été un cruel frein à la progression du projet. Il est bien souvent nécessaire de chercher pendant des heures avant de trouver une information sur une fonctionnalité spécifique et ce ne sera généralement pas sur les pages de documentation de {\Large \textsc{nVidia}} que l'information sera trouvée.
\paragraph{}Ce qui ressort finalement de la mise en place des solutions techniques du moteur CUDA est qu'il faudrait certainement plus de temps pour tester entièrement chacun des aspects de la gestion de la mémoire, des threads et des caches avant de pouvoir proposer une solution vraiment très efficace pour du calcul sur carte graphique.
